package com.yiwenup.struct._06_graph.base;

import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * 图接口：封装图的方法
 **/
public interface Graph<V, W> {
    /**
     * 顶点个数
     */
    int vertexSize();

    /**
     * 边条数
     */
    int edgeSize();

    /**
     * 添加顶点
     */
    void addVertex(V v);

    /**
     * 添加边
     */
    void addEdge(V from, V to);

    /**
     * 添加边（带权值）
     */
    void addEdge(V from, V to, W weight);

    /**
     * 删除顶点
     */
    void removeVertex(V v);

    /**
     * 删除边
     */
    void removeEdge(V from, V to);

    /**
     * 广度优先
     */
    void bfs(V begin, VertexVisitor<V> visitor);

    /**
     * 深度优先
     */
    void dfs(V begin, VertexVisitor<V> visitor);

    /**
     * AOV - 拓扑排序
     */
    List<V> topologiccalSort();

    /**
     * 最小生成树
     */
    Set<EdgeInfo<V, W>> mst();

    /**
     * 最短路径 - 单源
     */
    Map<V, W> shortestPath(V begin);

    /**
     * 最短路径 - 单源
     */
    Map<V, PathInfo<V, W>> shortestPathInfo(V begin);

    void print();

    interface VertexVisitor<V> {
        boolean visit(V val);
    }

    interface WeightManager<W> {
        int compare(W w1, W w2);
        W add(W w1, W w2);
    }

    class PathInfo<V, W> {
        // 路径总权值
        public W weight;
        // 路径集合
        public List<EdgeInfo<V, W>> edgeInfos = new LinkedList<>();

        public W getWeight() {
            return weight;
        }

        public void setWeight(W weight) {
            this.weight = weight;
        }

        public List<EdgeInfo<V, W>> getEdgeInfos() {
            return edgeInfos;
        }

        public void setEdgeInfos(List<EdgeInfo<V, W>> edgeInfos) {
            this.edgeInfos = edgeInfos;
        }

        @Override
        public String toString() {
            return "PathInfo{" +
                    "weight=" + weight +
                    ", edgeInfos=" + edgeInfos +
                    '}';
        }
    }

    class EdgeInfo<V, W> {
        private V from;
        private V to;
        private W weight;

        EdgeInfo(V from, V to, W weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        public V getFrom() {
            return from;
        }

        public void setFrom(V from) {
            this.from = from;
        }

        public V getTo() {
            return to;
        }

        public void setTo(V to) {
            this.to = to;
        }

        public W getWeight() {
            return weight;
        }

        public void setWeight(W weight) {
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "EdgeInfo{" +
                    "from=" + from +
                    ", to=" + to +
                    ", weight=" + weight +
                    '}';
        }
    }
}
